In the following description, references to picture signals will be understood to encompass information signals that represent still or moving pictures. Conventionally, spatial filtering is applied to picture signals in the spatial domain. The term spatial filtering as used in this disclosure refers to any operation performed by means of a linear convolution between an information signal and a linear convolution kernel.
In recent years, a number of efficient ways of compressing picture signals have been developed, and reductions in the cost of computers and digital signal processors have brought practical implementations of such compression schemes with the budgets of both the consumer and the professions. Compressing the picture signal reduces the amount of storage capacity required to store the picture signal or reduces the transmission bandwidth required to transmit the picture signal. A spatial filter designed to filter picture signals in the spatial domain will not produce the desired results when applied directly to compressed picture signals. A different approach is required to apply spatial filtering to compressed picture signals.
One approach is to expand the compressed picture signal to the spatial domain, apply the spatial filtering in the spatial domain using a conventional spatial domain filter, and re-compress the filtered picture signal. This approach will be called the straightforward approach. A flow chart of the straightforward approach is shown in FIG. 1. Initially, a compressed picture signal representing a still or moving picture is stored on a disk 12. Alternatively, the picture signal may be received via a communication link or some other means. The picture signal is compressed using one of any number of industry standard compression schemes, for example, JPEG, MPEG, H.261 or H.263. Many of the standard compression schemes use an orthogonal transform, such as a discrete cosine transform (DCT), to convert the blocks of picture data constituting the picture signal from the spatial domain to the frequency domain. The resulting blocks of DCT coefficients have substantially fewer DCT coefficients of a significant magnitude than the number of elements of significant magnitude in the original blocks of picture data. This is especially true when the original block of picture data represents part of the picture lacking in spatial detail. Consequently, orthogonally transforming the blocks of picture data and quantizing the resulting transform coefficients compresses the picture data, since fewer bits are required to represent the quantized DCT coefficients than are required to represent the original picture data.
Applying a DCT to two-dimensional 8.times.8 blocks of picture data converts the block {x(n,m)} in the spatial domain into a corresponding matrix of DCT coefficients {X(k,l)} in the frequency domain according to the following equation: ##EQU1## where c(k)=1/.sqroot.2 for k=0, and c(k)=1 for k&gt;0.
Conventional approaches to applying spatial filtering to a picture signal do not operate on the compressed picture signal, i.e., on the blocks of DCT coefficients. Instead, the blocks of DCT coefficients are transformed from the frequency domain back to the spatial domain in step 14. If the compression scheme uses a discrete cosine transform, the expansion scheme uses an inverse discrete cosine transform defined by the following equation: ##EQU2##
Once the compressed picture signal has been returned to the spatial domain, the conventional spatial filtering techniques indicated in block 16 can be used to apply the desired spatial filtering to the picture signal. The filtered picture signal is then re-compressed, as indicated in block 18. If, after compression, the filtered picture signal is to be compatible with the original compressed picture signal, the filtered picture signal should be re-compressed using the same compression scheme as was used to generate the original compressed picture signal. The compressed filtered picture signal is stored back on the disk 20, or may be transmitted elsewhere without storing it. Although the disks 12 and 20 are shown as separate devices, they can in fact be one and the same.
The problem with the straightforward approach is that it is computationally intensive. As described above, the compressed picture signal must be expanded, spatially filtered, and then re-compressed each time spatial filtering is applied. Savings in the computational resources required to perform such spatial filtering would be achieved if the spatial filtering could be performed on the compressed picture signal, i.e., if the spatial filtering could be performed on the blocks of DCT coefficients constituting the compressed picture signal. This would allow the expansion and re-compression processing performed by blocks 14 and 18, respectively, to be eliminated. This approach would only be desirable, however, if performing the spatial filtering in the DCT domain required fewer computational resources than those required by the conventional approach.
Past work on spatial filtering in the DCT domain has largely concentrated on convolution-multiplication properties (CMP's) of the DCT, and by analogy to the well-known CMP of the discrete Fourier transform (DFT). In Image Enhancement Using Cosine Transform Filtering, IMAGE SCI. MATH. SYMP., Monterey, Calif., November 1976, W. H. Chen and S. C. Fralick showed that coefficient-by-coefficient multiplication in the DCT domain corresponds to circular convolution of three time domain (or spatial domain) sequences. One of these sequences is a fixed undesired sequence that can be eliminated by an appropriate modification of the DCT domain filter coefficients. In Low-Pass Filtering in the Cosine Transform Domain, INT. CONF. ON COMMUN., Seattle, Wash., pp. 37.7.1-37.7.5, June 1980, K. N. Ngan and R. J. Clark applied this property to low-pass filtering images. Others have simplified significantly the CMP of Chen and Fralick. For example, see B. Chitpraset and K. R. Rao, Discrete Cosine Transform Filtering, 19 SIGNAL PROCESSING, 233-245, (1990). Their method, however, is still applicable only to a particular type of convolution called symmetric convolution rather than the more desirable linear convolution. It is known that the above-mentioned symmetric convolution causes block edge artifacts. More recently, in Symmetric Convolution and Discrete Sine and Cosine Transforms, SP-42 IEEE TRANS. ON SIGNAL PROCESSING, 1038-1051, (1994 May), S. A. Martucci described a complete set of symmetrical/antisymmetrical convolution routines for a family of discrete trigonometrical transforms, including the DCT. Martucci's method can be modified to obtain a linear convolution by appropriate zero padding in the convolution domain. However, Martucci's approach cannot be used directly or efficiently in the above-mentioned DCT-domain spatial filtering applications since the DCT domain data are already given without prior zero padding in the spatial domain.
In Transform Domain Filtering Based on Pipelining Structure, SP-40 IEEE TRANS. ON SIGNAL PROCESSING, 2061-2064, (1992 August), J. B. Lee and B. G. Lee described an alternative to the CMP approach that uses a simple algebraic approach to derive a transform-domain linear convolution filter and that can be implemented using a pipeline hardware architecture. The Lee and Lee approach precomputes the product of the operator matrices corresponding to inverse DCT (IDCT), the convolution, and the DCT, and then uses this combined operator matrix directly in the DCT domain. In this, the contributions of neighboring DCT data blocks are incorporated in a way similar to that of the overlap and add (OLA) method. In Manipulation and Compositing of MC-DCT Compressed Video, 13 IEEE J. SELECTED AREAS IN COMMUNICATIONS, 1-11 (1995 January), S. F. Chang and D. G. Messerschmitt proposed a similar approach by using the distributive property of the DCT with respect to matrix multiplication. A more thorough study of this approach, in combination with down sampling, was described by Neri et al. in Inter-Block Filtering and Down Sampling in DCT Domain, 6 SIGNAL PROCESSING: IMAGE COMMUNICATION, 303-317, (1994). The problem with each of these approaches is that they are still relatively computationally intensive, which causes filtering in the DCT domain to be slow.
In U.S. patent application Ser. No. 08/612,513, filed on Mar. 6 1996, entitled A Fast Method and Apparatus for Filtering Compressed Images in the DCT Domain, and assigned to the assignee of the present application, one of the inventors of this application (Merhav) and V. Bhaskharan describe a spatial filter for picture signals that operates in the DCT domain. Matrices obtained by performing a double butterflying operation on the input blocks of DCT coefficients are multiplied by multiplying matrices. The multiplying matrices are obtained by applying a discrete cosine transform to the input kernel matrices and then performing a butterflying operation on the resulting DCT coefficients. This filter has the advantage of being less computationally intense than the approaches described above, especially when the blocks of DCT coefficients are "sparse." In this disclosure, blocks of DCT coefficients are defined as being sparse when most of the DCT coefficients in the block have a value of zero. The reduced computational intensity of the filter arises because the multiplying matrices derived from the input kernel matrices are relatively sparse. However, the characteristics of the filter disclosed by Merhav and Bhaskharan are defined by a noncausal-symmetric kernel only. Moreover, it would be desirable if the filter could be made to operate more quickly in relevant applications.
It should be noted that the term symmetric is generally used in the art to denote filter kernels that are symmetrical about the origin. Some of the filter kernels described in this disclosure are symmetrical about a point other than the origin, and will be identified by the term causal symmetric. Filter kernels that are symmetric in the conventional sense will be described in this disclosure as non-causal symmetric to distinguish them from causal symmetric filter kernels.
It would be advantageous for the filter characteristics of a spatial filter operating in the DCT domain to be defined by any type of kernel, causal or non-causal; symmetric or non-symmetric. It would also be advantageous if the number of computational operations required to perform the spatial filtering operation to be further reduced.